// Dwarf.Unmanaged.Serial.cpp : Defines the entry point for the console application.
//

#include "Dwarf.Unmanaged.Mpi.h"

using namespace std;

// The settings for this dwarf.
static Settings* settings;

//Init & fill neigbourhood array
static inline void constructNeighborhood(Solver *ugsolver)
{       
    //Init map
    Neighborhood *neighborhood = new Neighborhood();
    for (unsigned int i = 0; i < ugsolver->numVertex; i ++)
    {
        neighborhood->insert(make_pair( i, new SetOfVertex() ));
    }

    //Insert verteces into map
    for (unsigned int j = 0; j < ugsolver->numTriangles; j ++)
    {
        ((SetOfVertex*)neighborhood->find(ugsolver->triangles[0][j])->second)->insert(ugsolver->triangles[1][j]);
        ((SetOfVertex*)neighborhood->find(ugsolver->triangles[0][j])->second)->insert(ugsolver->triangles[2][j]);

        ((SetOfVertex*)neighborhood->find(ugsolver->triangles[1][j])->second)->insert(ugsolver->triangles[0][j]);
        ((SetOfVertex*)neighborhood->find(ugsolver->triangles[1][j])->second)->insert(ugsolver->triangles[2][j]);

        ((SetOfVertex*)neighborhood->find(ugsolver->triangles[2][j])->second)->insert(ugsolver->triangles[0][j]);
        ((SetOfVertex*)neighborhood->find(ugsolver->triangles[2][j])->second)->insert(ugsolver->triangles[1][j]);
    }

    //Copy from map to array
    for (unsigned int i = 0; i < ugsolver->numVertex; i ++)
    {
        SetOfVertex *vSet = (SetOfVertex*)neighborhood->find(i)->second;
        ugsolver->numNeighbors[i] = (int)vSet->size();
        ugsolver->neighborhood[i] = new unsigned int[ugsolver->numNeighbors[i]];

        int j = 0;
        for( SetOfVertex::iterator iter = vSet->begin(); iter != vSet->end(); iter++ ) 
        {		
            ugsolver->neighborhood[i][j ++] = *iter;
	    }
    }

    //Dispose map
    for( Neighborhood::iterator iter = neighborhood->begin(); iter != neighborhood->end(); iter++ ) 
    {		
	    delete iter->second;
    }
}

//Construct array of proc's numbers of shadow (boundary) vertices for specified proc
static inline void constructShadowProcSetForVertex(
    Solver *ugsolver,                               //Instance of Solver
    unsigned int *numProcessVertices,               //Number of vertices for each process
    unsigned int **vertices,                        //Vertices for each process
    SetOfVertex *vSet,                              //All vertices of processorNum
    unsigned int *tempProcNumbers,                  //Output array
    unsigned int processorNum)                      //Number of specified proc
{
    int k = 0;
    //Loop for all vertices of processorNum
    for( SetOfVertex::iterator iter = vSet->begin(); iter != vSet->end(); iter++ )
    {
        //Loop for all processors except processorNum
        for (int j = 0; j < ugsolver->commSize; j++)
        {
            if (j == (int)processorNum) continue;

            unsigned int l = 0;
            //Loop for all vertices of j process
            for ( ;l < numProcessVertices[j]; l ++)
            {
                if (vertices[j][l] == *iter)
                {
                    tempProcNumbers[k ++] = j;
                    break;
                }
            }

            if (l < numProcessVertices[j] && vertices[j][l] == *iter)
            {
                break;
            }
        }
    }
}

//Construct array of shadow (boundary) vertices for specified proc
static inline void constructShadowSetForVertex(
    Solver *ugsolver,                           //Instance of Solver
    unsigned int *numProcessVertices,           //Number of vertices for each process
    unsigned int **vertices,                    //Vertices for each process
    SetOfVertex *vSet,                          //All vertices of processorNum
    unsigned int processorNum)                  //Number of specified proc
{
    //Add all neighbors
    for (unsigned int j = 0; j < numProcessVertices[processorNum]; j ++)
    {
        for (unsigned int k = 0; k < ugsolver->numNeighbors[vertices[processorNum][j]]; k ++)
        {
            vSet->insert(ugsolver->neighborhood[vertices[processorNum][j]][k]);
        }
    }
    //Remove own vertices
    for (unsigned int j = 0; j < numProcessVertices[processorNum]; j ++)
    {
        vSet->erase(vertices[processorNum][j]);
    }
}

//Split graph of vertices on random parts
static inline void randomGraphDivision(
    Solver *ugsolver,                           //Instance of Solver
    unsigned int *numProcessVertices,           //Number of vertices for each process
    unsigned int **vertices)                    //Vertices for each process
{
    //Init array
    for (int i = 0; i < ugsolver->commSize; i ++)
    {
        numProcessVertices[i] = 0;
    }

    //Compute number of vertices for each process
    for (unsigned int i = 0; i < ugsolver->numVertex; i ++)
    {
        numProcessVertices[i / (ugsolver->numVertex / ugsolver->commSize) % ugsolver->commSize] ++;
    }

    //Init arrays
    for (int i = 0; i < ugsolver->commSize; i ++)
    {
        vertices[i] = new unsigned int[numProcessVertices[i]];

        numProcessVertices[i] = 0;
    }

    //Split graph
    for (unsigned int i = 0; i < ugsolver->numVertex; i ++)
    {
        int h = i / (ugsolver->numVertex / ugsolver->commSize) % ugsolver->commSize;
        vertices[h][numProcessVertices[h] ++] = i;
    }        
}

//Let G = (V,E) be a graph and X, Y of V with X and Y = empty set and X or Y = V .
//For x of X denote with I(x) the inner costs, i.e. the number of edges
//(x, z) of E with z of X \ {x}. Analogously we define I(y) for y of Y .
static inline unsigned int computVertexInnerCost(
    Solver *ugsolver,                       //Instance of Solver
    unsigned int *numProcessVertices,       //Number of vertices for each process
    unsigned int **vertices,                //Vertices for each process
    unsigned int vertex)                    //Current vertex
{
    unsigned int count = 0;
    int proc = 0;
    unsigned int i;

    //Find process of current vertex
    for (; proc < ugsolver->commSize; proc++)
    {
        i = 0;
        for (; i < numProcessVertices[proc]; i++)
        {
            if (vertices[proc][i] == vertex) break;
        }

        if (i < numProcessVertices[proc] && vertices[proc][i] == vertex) break;
    }

    //Count inner edges for vertex
    for (unsigned int j = 0; j < ugsolver->numNeighbors[vertex]; j++)
    {
        i = 0;
        for (; i < numProcessVertices[proc]; i++)
        {
            if (vertices[proc][i] == ugsolver->neighborhood[vertex][j]) 
            {
                count++;
                break;
            }
        }
    }

    return count;
}

//For x of X, y of Y let S(x, y) := O(x) - I(x) + O(y) - I(y) - 2w(x, y)
//Where O - outer cost, I - inner cost, w(x,y) = 1, if (x, y) from E and 0, otherwise
static inline unsigned int computVerticesCost(
    Solver *ugsolver,                           //Instance of Solver
    unsigned int *numProcessVertices,           //Number of vertices for each process
    unsigned int **vertices,                    //Vertices for each process
    unsigned int x, unsigned int y)             //Two vertices
{
    unsigned int ix = computVertexInnerCost(ugsolver, numProcessVertices, vertices, x);
    unsigned int ox = ugsolver->numNeighbors[x] - ix;

    unsigned int iy = computVertexInnerCost(ugsolver, numProcessVertices, vertices, y);
    unsigned int oy = ugsolver->numNeighbors[y] - iy;

    bool w = false;

    for (unsigned int i = 0; i < ugsolver->numNeighbors[x]; i++)
    {
        if (ugsolver->neighborhood[x][i] == y) 
        {
            w = true;
            break;
        }
    }

    return ox - ix + oy - iy - (w ? 2 : 0);
}

//Modified Simple-Greedy-Algorithm
//
// 1 Choose x of X, y of Y with Vertices Cost > 0
// 2 Swap vertices x and y
// 3 Repeat steps 2 and 3, until there are no x of X, y of Y with Vertices Cost > 0
//
//Algorithm limited by 10000 iterations
static inline void simpleGreedyAlgorithmSolver (
    Solver *ugsolver,                           //Instance of Solver
    unsigned int *numProcessVertices,           //Number of vertices for each process
    unsigned int **vertices)                    //Vertices for each process
{
    bool converted = false;

    unsigned int k = 0;

    while (!converted)
    {
        converted = true;

        for (int proc1 = 0; proc1 < ugsolver->commSize; proc1++)
        {
            int proc2 = (proc1 + 1) % ugsolver->commSize;

            for (unsigned int i = 0; i < numProcessVertices[proc1]; i++)
            {
                for (unsigned int j = 0; j < numProcessVertices[proc2]; j++)
                {
                    //Limit 10000 iterations
                    if (k++ > 10000) return;

                    //Swap current vertices if Vertices cost > 0
                    if (computVerticesCost(ugsolver, numProcessVertices, vertices, vertices[proc1][i], vertices[proc2][j]) > 0)
                    {
                        unsigned int vertex = vertices[proc1][i];
                        vertices[proc1][i] = vertices[proc2][j];
                        vertices[proc2][j] = vertex;

                        converted = false;
                    }
                }
            }
        }
    }
}

//Split graph & distribute parts to processes
static inline void splitGraph(Solver *ugsolver)
{
    MPI_Status status; 

    if (ugsolver->isRootThread)
    {
        //first random graph division 
        unsigned int *numProcessVertices = new unsigned int [ugsolver->commSize];
        unsigned int **vertices = new unsigned int *[ugsolver->commSize];

        randomGraphDivision(ugsolver, numProcessVertices, vertices);

        simpleGreedyAlgorithmSolver(ugsolver, numProcessVertices, vertices);

        //destribution sub-graphs to processes
        for (int i = 1; i < ugsolver->commSize; i++)
        {            
            //send count of vertices for process i
            MPI_Send(numProcessVertices + i, 1, MPI_UNSIGNED, i, i, MPI_COMM_WORLD);

            //send numbers of vertices for process i
            MPI_Send(vertices[i], numProcessVertices[i], MPI_UNSIGNED, i, i, MPI_COMM_WORLD);

            //values of vertices are being sended to process i
            double *tempValues = new double[numProcessVertices[i]];
            for (unsigned int j = 0; j < numProcessVertices[i]; j ++)
            {
                tempValues[j] = ugsolver->value[vertices[i][j]];
            }
            MPI_Send(tempValues, numProcessVertices[i], MPI_DOUBLE, i, i, MPI_COMM_WORLD);
            delete tempValues;

            //send neighbor's numbers
            for (unsigned int j = 0; j < numProcessVertices[i]; j ++)
            {
                MPI_Send(ugsolver->numNeighbors + vertices[i][j], 1, MPI_UNSIGNED, i, i, MPI_COMM_WORLD);
                MPI_Send(
                    ugsolver->neighborhood[vertices[i][j]],                
                    ugsolver->numNeighbors[vertices[i][j]], MPI_UNSIGNED, i, i, MPI_COMM_WORLD);
            }            

            //numbers of shadow vertices are being sended to process i
            SetOfVertex *vSet = new SetOfVertex();

            constructShadowSetForVertex(ugsolver, numProcessVertices, vertices, vSet, i);

            unsigned int *tempvertices = new unsigned int[vSet->size()];
            unsigned int k = 0;
            for( SetOfVertex::iterator iter = vSet->begin(); iter != vSet->end(); iter++ ) 
            {		
                tempvertices[k ++] = *iter;
	        }
            MPI_Send(&k, 1, MPI_UNSIGNED, i, i, MPI_COMM_WORLD);
            MPI_Send(tempvertices, (int)vSet->size(), MPI_UNSIGNED, i, i, MPI_COMM_WORLD);

            //proc numbers of shadow vertices are being sended to process i            
            constructShadowProcSetForVertex(ugsolver, numProcessVertices, vertices, vSet, tempvertices, i);

            MPI_Send(tempvertices, (int)vSet->size(), MPI_UNSIGNED, i, i, MPI_COMM_WORLD);

            delete tempvertices;
            delete vSet;
        }    

        //computation of root data

        //values of vertices for root process 
        ugsolver->localNumValue = new std::map<unsigned int, double>();
        for (unsigned int j = 0; j < numProcessVertices[0]; j ++)
        {
            ugsolver->localNumValue->insert( make_pair(vertices[0][j], ugsolver->value[vertices[0][j]]));
        }

        //copy neighbor's numbers into localNeighborhood
        ugsolver->localNeighborhood = new Neighborhood();
        for (unsigned int j = 0; j < numProcessVertices[0]; j ++)
        {            
            SetOfVertex *vSet = new SetOfVertex();
            for (unsigned int i = 0; i < ugsolver->numNeighbors[vertices[0][j]]; i ++)
            {
                vSet->insert(ugsolver->neighborhood[vertices[0][j]][i]);
            }
            ugsolver->localNeighborhood->insert(make_pair( vertices[0][j],  vSet));
        }   

        //numbers of shadow (boundary) vertices for root
        SetOfVertex *vSet = new SetOfVertex();
        constructShadowSetForVertex(ugsolver, numProcessVertices, vertices, vSet, 0);

        unsigned int *tempvertices = new unsigned int[vSet->size()];
        unsigned int k = 0;
        for( SetOfVertex::iterator iter = vSet->begin(); iter != vSet->end(); iter++ ) 
        {		
            tempvertices[k ++] = *iter;
        }

        ugsolver->shadowNumValue = new std::map<unsigned int, double>();
        for (unsigned int j = 0; j < vSet->size(); j ++)
        {
            ugsolver->shadowNumValue->insert( make_pair(tempvertices[j], 0));
        }

        //proc numbers of shadow (boundary) vertices for root
        unsigned int *tempProcNumbers = new unsigned int[vSet->size()];

        constructShadowProcSetForVertex(ugsolver, numProcessVertices, vertices, vSet, tempProcNumbers, 0);

        ugsolver->shadowNumProc = new std::map<unsigned int, unsigned int>();
        for (unsigned int j = 0; j < vSet->size(); j ++)
        {
            ugsolver->shadowNumProc->insert( make_pair(tempvertices[j], tempProcNumbers[j]));
        }

        //release memory

        delete tempProcNumbers;
        delete tempvertices;
        delete vSet;
        
        for (int i = 0; i < ugsolver->commSize; i ++)
        {
            delete vertices[i];
        }

        delete vertices;
        delete numProcessVertices;
    } 
    else
    {       
        unsigned int numVertices = 0;
        //receive count of vertices
        MPI_Recv(&numVertices, 1,  MPI_UNSIGNED, NUMBER_ROOT_PROCESS,  MPI_ANY_TAG,  MPI_COMM_WORLD, &status);

        unsigned int *vertices = new unsigned int [numVertices];
        //receive numbers of vertices
        MPI_Recv(vertices, numVertices,  MPI_UNSIGNED, NUMBER_ROOT_PROCESS,  MPI_ANY_TAG,  MPI_COMM_WORLD, &status);

        ugsolver->localNumValue = new std::map<unsigned int, double>();
        double *tempValues = new double[numVertices];
        //receive values of vertices
        MPI_Recv(tempValues, numVertices,  MPI_DOUBLE, NUMBER_ROOT_PROCESS,  MPI_ANY_TAG,  MPI_COMM_WORLD, &status);
        
        for (unsigned int j = 0; j < numVertices; j ++)
        {
            ugsolver->localNumValue->insert( make_pair(vertices[j], tempValues[j]));
        }
        delete tempValues;

        ugsolver->localNeighborhood = new Neighborhood();
        //receive Neighborhood 
        for (unsigned int j = 0; j < numVertices; j ++)
        {            
            SetOfVertex *vSet = new SetOfVertex();
            unsigned int numNeighbors = 0;
            MPI_Recv(&numNeighbors, 1,  MPI_UNSIGNED, NUMBER_ROOT_PROCESS,  MPI_ANY_TAG,  MPI_COMM_WORLD, &status);
            unsigned int *neighbors = new unsigned int[numNeighbors];
            MPI_Recv(neighbors, numNeighbors,  MPI_DOUBLE, NUMBER_ROOT_PROCESS,  MPI_ANY_TAG,  MPI_COMM_WORLD, &status);
            for (unsigned int i = 0; i < numNeighbors; i ++)
            {
                vSet->insert(neighbors[i]);
            }
            ugsolver->localNeighborhood->insert(make_pair( vertices[j],  vSet));
        }

        delete vertices;

        //Receive shadow vertices
        MPI_Recv(&numVertices, 1,  MPI_UNSIGNED, NUMBER_ROOT_PROCESS,  MPI_ANY_TAG,  MPI_COMM_WORLD, &status);

        vertices = new unsigned int [numVertices];
        MPI_Recv(vertices, numVertices,  MPI_UNSIGNED, NUMBER_ROOT_PROCESS,  MPI_ANY_TAG,  MPI_COMM_WORLD, &status);

        ugsolver->shadowNumValue = new std::map<unsigned int, double>();
        for (unsigned int j = 0; j < numVertices; j ++)
        {
            ugsolver->shadowNumValue->insert( make_pair(vertices[j], 0));
        }

        ugsolver->shadowNumProc = new std::map<unsigned int, unsigned int>();
        unsigned int *tempProcNum = new unsigned int[numVertices];
        //Receive processors of shadow vertices
        MPI_Recv(tempProcNum, numVertices,  MPI_UNSIGNED, NUMBER_ROOT_PROCESS,  MPI_ANY_TAG,  MPI_COMM_WORLD, &status);
        for (unsigned int j = 0; j < numVertices; j ++)
        {
            ugsolver->shadowNumProc->insert( make_pair(vertices[j], tempProcNum[j]));
        }
        delete tempProcNum;
    }

    //Fill temp map
    ugsolver->localNumValueTemp = new std::map<unsigned int, double>();
    for( std::map<unsigned int, double>::iterator iter = ugsolver->localNumValue->begin(); iter != ugsolver->localNumValue->end(); iter++ )
    {
        ugsolver->localNumValueTemp->insert(make_pair(iter->first,iter->second));
    }
}

// Get settings from the command line.
static int getSettings(int argc, char** argv, Solver *ugsolver) 
{
    int error = 0;
    if (ugsolver->isRootThread) 
    {
        settings = new Settings();
        if (settings->init(argc,argv,ugsolver))         //Parse all arguments for dwarf.
        {            
            delete settings;
            error = 1;
        }

        constructNeighborhood(ugsolver);        
    }    

    //Distribute error if that occurred while parsing.
    MPI_Bcast(&error, 1, MPI_INT, NUMBER_ROOT_PROCESS, MPI_COMM_WORLD); 

    if (error) return -1;

    //Distribute epsilon.
    MPI_Bcast(&ugsolver->epsilon, 1, MPI_DOUBLE, NUMBER_ROOT_PROCESS, MPI_COMM_WORLD);

    splitGraph(ugsolver);

    return 0;
}

// Point of the program start.
void main(int argc, char** argv)
{   

    Solver* ugsolver = new Solver(); 

    if (ugsolver->commSize == 1) 
    {
        delete ugsolver;
        printf("Only one mpi process.");
        exit(-1);
    }

    if (getSettings(argc, argv, ugsolver))         // Get settings from the command line.
    {
        delete ugsolver;
        exit(-1);
    }

    MPI_Barrier(MPI_COMM_WORLD);

    if (ugsolver->isRootThread) 
    {
        settings->start();                          // Start new time count.
    }

	ugsolver->solve();                             // Solve the current problem.

    MPI_Barrier(MPI_COMM_WORLD);

    if (ugsolver->isRootThread) 
    {
        settings->finish(ugsolver);                // Stop the time count and write results.
        delete settings;
    }

    delete ugsolver;
}